package com.tlvip.leetcode;

/**
 * <p>description：</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： 统计n以内的素数个数
 * 素数只能被1和自身整除的自然数，0，1除外
 * 重点考察：埃筛法
 * </p>
 * Date 2022/5/8</p>
 * Author mac
 *
 * @version 1.0
 */
public class CountPrime {

    public static void main(String[] args) {
        int num = 100000;
        System.out.println(countPrime(num));
        System.out.println(eratosthenes(num));
    }

    /**
     * 素数
     * 非素数（合数）
     * <p>
     * 将合数标记为true，j = i * i 从 2 * i优化而来，系数2会随着遍历增加(j += i，相当于递增了系数2)，
     * 每一个合数都会有一个比本身要小的因子（0，1除外），2 * i必然会遍历到这两个因子
     * <p>
     * 当2递增到大于根号n时，其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n，实际上在i递增
     * 的过程中已经计算过了，i实际上就相当于根号n
     *
     * @param n 给定的数字，统计其包含的素数个数
     * @return 素数个数
     */
    public static int eratosthenes(int n) {
        boolean isPrime[] = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                // j 是合数标记位
                for (int j = i * i; j < n; j += i) {
                    try {
                        isPrime[j] = true;
                    } catch (Exception e) {
                        System.out.println(j);
                        e.printStackTrace();
                    }

                }
            }
        }
        return count;
    }

    /**
     * 暴力算法统计
     *
     * @param num 给定数字，需要统计素数个数的数字
     * @return 素数个数
     */
    public static int countPrime(int num) {
        int count = 0;
        for (int i = 2; i <= num; i++) {
            if (checkPrime(i)) {
                count++;
            }
        }
        return count;
    }

    private static boolean checkPrime(int num) {
        boolean flag = true;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                flag = false;
                break;
            }
        }
        return flag;
    }

}
